package AnswerOfComent;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

public class Tencent_215_findKthLargest {
    /**
     * 大神题解
     * 使用快排的思想來實現
     * 这是最优的一种实现方式
     */
    private static Random random = new Random(System.currentTimeMillis());
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            int index = partition(nums, left, right);
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
    }

    // 在区间 nums[left..right] 区间执行 partition 操作
    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    /**
     * 最小堆的解法，可惜我不懂最小堆
     */
    public class Solution {

        public int findKthLargest(int[] nums, int k) {
            int len = nums.length;
            // 使用一个含有 k 个元素的最小堆，PriorityQueue 底层是动态数组，为了防止数组扩容产生消耗，可以先指定数组的长度
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(a -> a));
            // Java 里没有 heapify ，因此我们逐个将前 k 个元素添加到 minHeap 里
            for (int i = 0; i < k; i++) {
                minHeap.offer(nums[i]);
            }

            for (int i = k; i < len; i++) {
                // 看一眼，不拿出，因为有可能没有必要替换
                Integer topElement = minHeap.peek();
                // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
                if (nums[i] > topElement) {
                    // Java 没有 replace()，所以得先 poll() 出来，然后再放回去
                    minHeap.poll();
                    minHeap.offer(nums[i]);
                }
            }
            return minHeap.peek();
        }
    }
}
